package com.person.leetcode.editor.cn;

import java.util.*;

/**
 * 954.二倍数对数组
 * 2022-04-01 10:21:28
 **/
public class Sequence_0954_ArrayOfDoubledPairs {
    public static void main(String[] args) {
        Solution solution = new Sequence_0954_ArrayOfDoubledPairs().new Solution();
        int[] arr = {6, 5, -8, 1};
        //List<Integer> list = Arrays.stream(arr).boxed().collect(Collectors.toList());
        List<Integer> list = new ArrayList<>();
        for (int i : arr) {
            list.add(i);
        }
        Collections.sort(list, (a, b) -> {
            return Math.abs(a) - Math.abs(b);
        });
        System.out.println(list);
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {

        public boolean canReorderDoubled(int[] arr) {
            //1.使用绝对值排序
            //2.用hash记录每个值的数量

            if (arr.length % 2 != 0) {
                return false;
            }

            HashMap<Integer, Integer> hash = new HashMap<>();
            for (int i : arr) {
                //   key 值 value 数量
                hash.put(i, hash.getOrDefault(i, 0) + 1);
            }
            if (hash.getOrDefault(0, 0) % 2 != 0) {
                //零的个数为奇数
                return false;
            }

            //根据去重后的key排序
            ArrayList<Integer> list = new ArrayList<>();
            for (Integer integer : hash.keySet()) {
                list.add(integer);
            }

            Collections.sort(list, (a, b) -> {
                return Math.abs(a) - Math.abs(b);
            });

            for (Integer x : list) {

                if (hash.getOrDefault(2 * x, 0) < hash.get(x)) {
                    return false;
                }
                hash.put(2 * x, hash.getOrDefault(2 * x, 0) - hash.get(x));
            }

            return true;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
